package com.yang.linkedlist_;

public class LinkedNodeTest {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addNode(1);
        myLinkedList.addNode(2);
        myLinkedList.printf();
        System.out.println(myLinkedList.detectCycle(myLinkedList.head.next));
        System.out.println(myLinkedList.detectCycle(myLinkedList.head.next.next));
        myLinkedList.printf();
    }
}


// 按照数组来理解
class ListNode{
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList{
    int size;  // 记录链表元素数
    ListNode head; // 虚拟头结点

    // 初始化建立一个头结点
    public MyLinkedList(){
        size = 0;
        head = new ListNode(0);
    }

    // 增加一个元素
    public void addNode(int val){
        // 新建加入元素节点
        ListNode newNode = new ListNode(val);
        ListNode pre = head;
        // 如果虚拟头节点后面没有节点则为空
        if(pre.next==null){
            pre.next = newNode;
            size++;
            return;
        }
        // 如果当前节点不为空就一直循环
        // 为空就表示元素已经增加
        while(pre != null){
            pre = pre.next;
            if(pre.next == null){
                pre.next = newNode;
                size++;
                if (size == 2){
                    pre.next.next = head.next;
                }
                System.out.println("size="+size+"增加元素="+pre.next.val);
                return;
            }
        }
    }

    // 遍历打印链表
    public void printf(){
        ListNode pre = head;
        for (int i = 0; i < size; i++) {
            pre = pre.next;
            System.out.println(pre.val);
        }
    }

    public int get(int index){
        if(index < 0  ||  index >= size){
//            System.out.println("当前链表为空");
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i <= index; i++) {
            // i = 0时取出第一个数
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0,val);
    }

    public void addAtTail(int val) {
        addAtIndex(size,val);
    }

    // 在第index个元素前插入元素
   void addAtIndex(int index,int val){
       if(index > size){
//            System.out.println("当前链表为空");
           return;
       }
       if(index < 0){
           index = 0;
       }

       ListNode pre = head;
       // 找到要插入节点的前驱
       for (int i = 0; i < index; i++) {
           pre = pre.next;
       }
       size++;
       ListNode toAdd = new ListNode(val);
       toAdd.next = pre.next;
       pre.next = toAdd;
   }

   // 索引是始终比长度小于1的
 public void deleteAtIndex(int index){
        if(index < 0 || index >= size )
        {
            return;
        }
     size--;
     ListNode cur = head;
        for (int i = 0; i < index; i++) {
            // i = 0时取出第一个数
            cur = cur.next;
        }
            cur.next = cur.next.next;
   }

   // leetCode 206
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head.next;
        ListNode temp;
        while (cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return  head.next = pre;
    }

    // leetcode 24
    public ListNode swapPairs(ListNode head) {
        // 初始化一个虚拟头结点
        ListNode dummyNode = new ListNode(0);
        // 虚拟头结点指向头结点
        dummyNode.next = head;
        //
        ListNode pre = dummyNode;

        // 当理论意义上的1号和2号都存在的时候
        // 即还存在为交换的两两节点时，才会继续循环
        while (pre.next != null && pre.next.next != null){
            // 用来保存连接点
            ListNode temp;
            // 虚拟头结点指向2号节点
            pre.next = head.next;
            // 保存23之间的链条
            temp = head.next.next;
            // 2号指向1号
            head.next.next = head;
            // 1号指向3号
            head.next = temp;
            // pre表示号 即进位// !!!!注意此时head已经是相当于2号节点了！！！！
            pre = head;
            // head也进位表示3号
            head = head.next;
        }
        return  dummyNode.next;
    }

    // leetcode 19 移除倒数第几
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode slow = dummyNode;
        ListNode fast = dummyNode;
        for (int i = 0; i < n+1; i++) {
            fast = fast.next;
        }
        while (fast != null){
            // 双指针 fast先走n+1步  然后同时走，这样slow就是指向删除节点的前一个节点
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        size--;
        return dummyNode.next;
    }

    // leetCode面试题 求两链表交点
    // 有那么几个点
    // 不能直接操作各个head头 要通过新建node操作
    // 求完长度后新建node也要重新初始化 位置已经变了
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0, sizeB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null){
            curA = curA.next;
            sizeA++;
        }
        while (curB != null){
            curB = curB.next;
            sizeB++;
        }
        curA = headA;
        curB = headB;
        // 如果B的长度比A长就进行交换  提高代码可读性
        if(sizeB>sizeA){
            int temp;
            temp = sizeB;
            sizeB = sizeA;
            sizeA = temp;
            ListNode tempNode;
            tempNode = curB;
            curB = curA;
            curA = tempNode;
        }
        sizeA = sizeA - sizeB;

            for (int i = 0; i < sizeA; i++) {
                curA = curA.next;
            }
            while (curA != null){
                if(curA == curB){
                    return curA;
                }
                curA = curA.next;
                curB = curB.next;
            }
        return null;
    }

    // leetCode142 返回环形链表入口
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;

        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                while (index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
                // 这个是自己的写法  但是最好不要这样写 因为if必须放在前面然而我自己不知道这个bug查了半天
//                while (true){
//                    if (index1 == index2){
//                        return index1;
//                    }
//                    index1 = index1.next;
//                    index2 = index2.next;
//                }

            }
        }
        return null;
    }
}
